//水塘抽样
//对于第n个被找到的数，有1/n的概率以它为答案，这样则是(n-1)/n的概率以之前的数为答案，之前的数是答案的概率是1/(n-1)，相乘也是1/n
public class Solution398 {

    int[] nums;

    public Solution398(int[] nums) {
        this.nums=nums;
    }

    public int pick(int target) {
        int ans=-1;
        int c=0;
        for (int i=0;i<nums.length;i++) {
            if (nums[i]==target){
                c++;
                if ((int)(Math.random()*c)==0){
                    ans=i;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution398 solution398=new Solution398(new int[]{1,2,3,3,3});
        System.out.println(solution398.pick(3));
    }
}
